#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable:6031)


//https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
class Solution {
    TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int& rooti, int begin, int end)
    {
        if (begin > end)
            return nullptr;

        int i = begin;
        while (i <= end)
        {
            if (inorder[i] == postorder[rooti])
            {
                break;
            }
            i++;
        }
        TreeNode* newnode = new TreeNode(postorder[rooti--]);

        newnode->right = _buildTree(inorder, postorder, rooti, i + 1, end);
        newnode->left = _buildTree(inorder, postorder, rooti, begin, i - 1);

        return newnode;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        TreeNode* root = nullptr;
        int rooti = postorder.size() - 1;
        root = _buildTree(inorder, postorder, rooti, 0, inorder.size() - 1);

        return root;
    }
};